package code.notdo;

import com.sun.org.apache.bcel.internal.generic.SWAP;

import java.util.*;

/**
 * author : yeswater
 * date : 2023/12/6
 * <p>
 * 下一个排列: 整数的下一个字典序更大的排列 .  排序(所有成员)
 * 
 * 找到 :: 从低位到高位的第一个下降的数。
 */

public class T031 {
    public static void main(String[] args) {

    }

    /**
     * 从后往前找，找到第一个下降的位置，记为 k。注意k 以后的位置是降序的。 在样例中就是找到 3
     *
     * 从 k 往后找，找到最小的比 k 要大的数。 找到 4
     *
     * 将两者交换。注意此时 k 以后的位置仍然是降序的。
     *
     * 直接将 k 以后的部分翻转（变为升序）
     */
    public void nextPermutation(int[] nums) {
        int n = nums.length, k = n - 1;
        while (k - 1 >= 0 && nums[k - 1] >= nums[k]) k--;
        if (k == 0) {
            reverse(nums, 0, n - 1);
        } else {
            int u = k;
            while (u + 1 < n && nums[u + 1] > nums[k - 1]) u++;
            swap(nums, k - 1, u);
            reverse(nums, k, n - 1);
        }
    }

    void reverse(int[] nums, int a, int b) {
        int l = a, r = b;
        while (l < r)
            swap(nums, l++, r--);
    }

    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }
}
